﻿// 中缀表达式转后缀表达式（逆波兰表达式）并计算.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<stack>
#include<sstream>

using namespace std;

/// <summary>
/// 中缀表达式转逆波兰表达式
/// </summary>
/// <param name="expStr"></param>
/// <returns></returns>
string GetRPN(string expStr)
{
    int left = 0, right = 0;
	stack<char> stk;
	string res;
	while (right<expStr.size())
	{
		//用两个索引指针来截取数字并加入结果表达式
		while (right < expStr.size() && isdigit(expStr[right]))
			right++;
		if (right > left)
		{
			res += ' ' + expStr.substr(left, right - left);
		}

		//对符号进行判断（在下一个数字开头之前）并处理表达式
		while (right < expStr.size() && !isdigit(expStr[right]))
		{
			switch (expStr[right])
			{
			case '+':
				//当符号栈顶的运算优先级高于当前符号时处理栈顶符号并出栈
				while (!stk.empty() && (stk.top() == '*' || stk.top() == '/'))
				{
					res += stk.top();
					stk.pop();
				}
				stk.push('+');
				break;
			case '-':
				//当符号栈顶的运算优先级高于当前符号时处理栈顶符号并出栈
				while (!stk.empty() && (stk.top() == '*' || stk.top() == '/'))
				{
					res += stk.top();
					stk.pop();
				}
				stk.push('-');
				break;
			case '*':
				stk.push('*');
				break;
			case '/':
				stk.push('/');
				break;
			case '(':
				stk.push('(');
				break;
			case ')':
				//当前为闭括号时对栈顶在'('前的所有符号加在结果表达式后
				while (!stk.empty() && stk.top() != '(')
				{
					res += stk.top();
					stk.pop();
				}
				if (!stk.empty())
				{
					stk.pop();
				}
				break;
			default:
				break;
			}
			right++;
		}
		left = right;
		
	}

	//将剩下的除'('和')'符号追加到字符串尾
	while (!stk.empty())
	{
		char c = stk.top();
		if(c!='('&&c!=')')
			res += c;
		stk.pop();
	}
	return res;
}

/// <summary>
/// 计算逆波兰表达式
/// </summary>
/// <param name="expStr"></param>
/// <returns></returns>
int CalculationRPN(string expStr)
{
	stack<int> stk;
	int left = 0, right = 0;
	while (right < expStr.size())
	{
		while (right < expStr.size() && isdigit(expStr[right]))
			right++;
		if (left < right)
		{
			stringstream ss;
			ss << expStr.substr(left, right - left);
			int num;
			ss >> num;
			stk.push(num);
		}

		while (right<expStr.size()&&!isdigit(expStr[right]))
		{
			int num1, num2;
			switch (expStr[right])
			{
			case '+':
				num2 = stk.empty() ? 0 : stk.top();
				stk.pop();
				num1 = stk.empty() ? 0 : stk.top();
				stk.pop();
				stk.push(num1 + num2);
				break;
			case '-':
				num2 = stk.empty() ? 0 : stk.top();
				stk.pop();
				num1 = stk.empty() ? 0 : stk.top();
				stk.pop();
				stk.push(num1 - num2);
				break;
			case '*':
				num2 = stk.empty() ? 0 : stk.top();
				stk.pop();
				num1 = stk.empty() ? 0 : stk.top();
				stk.pop();
				stk.push(num1 * num2);
				break;
			case '/':
				num2 = stk.empty() ? 1 : stk.top();
				stk.pop();
				num1 = stk.empty() ? 0 : stk.top();
				stk.pop();
				stk.push(num1 / num2);
				break;
			default:
				break;
			}
			right++;
		}
		left = right;
	}
	return stk.top();
}

int main()
{
	string str = "(3+2*(8+2))*5";
	string res = GetRPN(str);
	int resNum = CalculationRPN(res);
	return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
